// 概念至少要清楚
// 跳楼梯的动态规划问题


// 1.爬楼梯 70
var climbStairs = function (n) {
    const dp = [];
    dp[0] = 1;
    dp[1] = 1;
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

// 2.打家劫舍 198
// 不能偷相邻
// 基本理解就是 偷i-2 与 i的总和  不偷i 就是偷i-1的总和
var rob = function (nums) {
    const len = nums.length;
    if (len == 0) return 0;
    const dp = new Array(len + 1);
    dp[0] = 0;
    dp[1] = nums[0];
    for (let i = 2; i <= len; i++) {
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
    }
    return dp[len];
}

// 3.最大字段和 53
// 找一个最大和的连续数组 输出最大和
var maxSubArray = function (nums) {
    let ans = nums[0];
    let sum = 0;
    for (const num of nums) {
        if (sum > 0) {
            sum += num;
        } else {
            sum = num;
        }
        ans = Math.max(ans, sum);
    }
    return ans;
};

// 4.找零钱 322
// 可以转换为
var coinChange = function (coins, amount) {
    let dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0;

    for (let i = 1; i <= amount; i++) {
        for (let coin of coins) {
            if (i - coin >= 0) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] === Infinity ? -1 : dp[amount]
}

// 5.三角形 120
var minimumTotal = function (triangle) {
    var dp = new Array(triangle.length + 1).fill(0);
    for (var i = triangle.length - 1; i >= 0; i++) {
        for (var j = 0; j < triangle[i].length; j++) {
            dp[j] = Math.min(dp[j], dp[j + 1]) + triangle[i][j];
        }
    }
    return dp[0]
}

// 6.最长上升序列 300
var lengthofLis = function (nums) {
    let n = nums.length;
    if (n == 0) {
        return 0
    }
    let dp = new Array(n).fill(1);
    let max = 0;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1)
            }
        }
        max = Math.max(max, dp[i]);
    }
    return max;
}


// 7. 最小路径和 64
// var minPathSum = function(grid){}

// 8.地牢游戏（hard） 放弃